package problems.contest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * <p></p>
 *
 * @author habitplus
 * @since 22:49, 2022/12/24
 */
public class BCT94 {

    /**
     * T1|2511. 最多可以摧毁的敌人城堡数目
     * <p>https://leetcode.cn/problems/maximum-enemy-forts-that-can-be-captured/</p>
     */
    public int captureForts(int[] forts) {
        int ret = 0;
        int pre = -1;

        for (int i = 0; i < forts.length; ++i) {
            if (forts[i] != 0) {
                if (pre != -1 && forts[pre] * forts[i] == -1) {
                    ret = Math.max(i - pre - 1, ret);
                }
                pre = i;
            }
        }

        return ret;
    }

    /**
     * T2|2512. 奖励最顶尖的 K 名学生
     * <p>https://leetcode.cn/problems/reward-top-k-students/</p>
     */
    public List<Integer> topStudents(String[] positive_feedback, String[] negative_feedback, String[] report, int[] student_id, int k) {
        HashSet<String> pf = new HashSet<>();
        HashSet<String> nf = new HashSet<>();

        for (String s : positive_feedback) pf.add(s);

        for (String s : negative_feedback) nf.add(s);

        int n = report.length;

        int[][] arr = new int[n][2];

        int score;

        for (int i = 0; i < n; ++i) {
            arr[i][0] = student_id[i];
            String[] ss = report[i].split(" ");
            score = 0;
            for (String s : ss) {
                if (pf.contains(s)) score += 3;
                else if (nf.contains(s)) --score;
            }
            arr[i][1] = score;
        }


        Arrays.sort(arr, (o1, o2) -> o1[1] == o2[1] ? o1[0] - o2[0] : o2[1] - o1[1]);

        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < k; ++i) {
            list.add(arr[i][0]);
        }

        return list;
    }


    /**
     * T3|2513. 最小化两个数组中的最大值
     * <p>https://leetcode.cn/problems/minimize-the-maximum-of-two-arrays/</p>
     */
    class Solution {
        int d1, d2, uniqueCnt1, uniqueCnt2;
        long lcm;

        public int gcd(int a, int b) {
            while (b != 0) {
                int tmp = a % b;
                a = b;
                b = tmp;
            }
            return a;
        }

        public boolean check(long mid) {
            long x1 = mid / d2 - mid / lcm;
            long x2 = mid / d1 - mid / lcm;
            long need1 = Math.max(0L, (long) uniqueCnt1 - x1);
            long need2 = Math.max(0L, (long) uniqueCnt2 - x2);
            long x12 = mid - mid / d1 - mid / d2 + mid / lcm;
            return x12 >= need1 + need2;
        }

        public int minimizeSet(int divisor1, int divisor2, int uniqueCnt1, int uniqueCnt2) {
            d1 = divisor1;
            d2 = divisor2;
            this.uniqueCnt1 = uniqueCnt1;
            this.uniqueCnt2 = uniqueCnt2;
            lcm = (long) d1 / gcd(d1, d2) * d2;

            long l = 0L;
            long r = (long) (1e18);
            while (l < r) {
                long mid = (l + r) / 2;
                if (check(mid)) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }

            return (int) l;
        }
    }
}
